package frist50;

import org.junit.jupiter.api.Test;

public class T0005$ {
    public String longestPalindrome(String s) {
        StringBuffer strb = new StringBuffer(s);
        for (int i = s.length(); i >= 0; i--) {
            strb.insert(i, '@');
        }
        int slen = s.length()*2+1;
        int[] p = new int[slen];
        int center = 0, maxRight = 0;
        int maxlen = 1, start = 0;
        for (int i = 0; i < slen; i++) {
            if (i < maxRight) {
                p[i] = Math.min(p[2 * center - i], maxRight - i);
            }
            int left = i - (p[i] + 1);
            int right = i + (p[i] + 1);
            while (left >= 0 && right < slen && strb.charAt(left) == strb.charAt(right)) {
                p[i]++;
                left--;
                right++;
            }

            if (i + p[i] > maxRight) {
                center = i;
                maxRight = i + p[i];
            }

            if (p[i] > maxlen) {
                maxlen = p[i];
                start = (i - maxlen) / 2;
            }
        }
        return s.substring(start, start + maxlen);
    }

    @Test
    public void test() {

        System.out.println(longestPalindrome("cbabad"));
        ;


    }


}
